package com.codebuffer.nowcoder;

import java.util.HashMap;
import java.util.Map;
import java.util.logging.Handler;

public class IsBalanced_Solution {

    public static boolean IsBalanced_Solution(TreeNode root) {
        Map<TreeNode,Integer> count = new HashMap();
        depth(root,count);
        return judge(root,count);
    }

    private static void depth(TreeNode root, Map<TreeNode, Integer> map) {
        if(null == root || "#".equals(root.val)){
            map.put(root,0);
            return;
        }
        depth(root.left,map);
        depth(root.right,map);
        map.put(root,Math.max(map.get(root.left),map.get(root.right))+1);
    }
    private static boolean judge(TreeNode root, Map<TreeNode, Integer> map) {
        if(null == root || "#".equals(root.val)){
            return true;
        }
        if(Math.abs(map.get(root.left)-map.get(root.right))>1){
            return false;
        }
        return judge(root.left,map)&&judge(root.right,map);
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.left = node6;

        System.out.println(IsBalanced_Solution(node1));
    }
}
